F.
cpp

#include <iostream>
#include <vector>

const int MOD = 10007;

// 矩阵乘法
std::vector<std::vector<int>>
matrixMultiply(const std::vector<std::vector<int>> &A, const std::vector<std::vector<int>> &B) {
    int rowsA = A.size();
    int colsA = A[0].size();
    int colsB = B[0].size();
    std::vector<std::vector<int>> result(rowsA, std::vector<int>(colsB, 0));
    for (int i = 0; i < rowsA; ++i) {
        for (int j = 0; j < colsB; ++j) {
            for (int k = 0; k < colsA; ++k) {
                result[i][j] = (result[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    return result;
}

// 矩阵快速幂
std::vector<std::vector<int>> matrixPower(const std::vector<std::vector<int>> &A, int n) {
    int size = A.size();
    std::vector<std::vector<int>> result(size, std::vector<int>(size, 0));
    for (int i = 0; i < size; ++i) {
        result[i][i] = 1;
    }
    std::vector<std::vector<int>> base = A;
    while (n > 0) {
        if ( n & 1 ) {
            result = matrixMultiply(result, base);
        }
        base = matrixMultiply(base, base);
        n >>= 1;
    }
    return result;
}

int main() {
    int N, M;
    while (std::cin >> N >> M) {
        std::vector<int> F(M);
        for (int i = 0; i < M; ++i) {
            std::cin >> F[i];
            F[i] = (F[i] % MOD + MOD) % MOD;
        }
        std::vector<int> a(M);
        for (int i = 0; i < M; ++i) {
            std::cin >> a[i];
            a[i] = (a[i] % MOD + MOD) % MOD;
        }

        // 初始化 S(0)
        int S0 = 0;
        for (int i = 0; i < M; ++i) {
            S0 = (S0 + F[i]) % MOD;
        }

        // 构造矩阵 A
        std::vector<std::vector<int>> A(M + 1, std::vector<int>(M + 1, 0));
        A[0][0] = 1;
        for (int i = 0; i < M; ++i) {
            A[0][i + 1] = a[i];
            A[1][i + 1] = a[i];
        }
        for (int i = 2; i <= M; ++i) {
            A[i][i - 1] = 1;
        }

        // 构造初始向量 X0
        std::vector<std::vector<int>> X0(M + 1, std::vector<int>(1, 0));
        X0[0][0] = S0;
        for (int i = 0; i < M; ++i) {
            X0[i + 1][0] = F[M - 1 - i];
        }

        // 计算 A^N
        std::vector<std::vector<int>> AN = matrixPower(A, N - M + 1);

        // 计算最终结果
        std::vector<std::vector<int>> result = matrixMultiply(AN, X0);
        std::cout << result[0][0] << std::endl;
    }
    return 0;
}